#include <iostream>
#include <string>
#include <vector>

using counttype = uint64_t;

class Generator
{
public:
    void EnumerateAll(int n, int C)
    {
        if (n < 0 || C < 2)
        {
            throw std::invalid_argument("n must be greater than 0 and C must be greater than 2.");
        }
        std::string result;
        EnuerateImpl(result, 0, n, C);
    }

    counttype Count(int n, int C)
    {
        if (n < 0 || C < 2 || C > 64)
        {
            throw std::invalid_argument("n must be greater than 0 and C must be greater than 2 and less than 64");
        }

        return CountImpl(n, C);
    }

private:
    // preCount is the count for how many consecutive 1s in result ending.
    void EnuerateImpl(std::string& result, int preCount, const int& n, const int& C)
    {
        if (result.size() == n)
        {
            std::cout << result << std::endl;
            return;
        }

        result.push_back('0');
        EnuerateImpl(result, 0, n, C);

        if (preCount < C - 1)
        {
            result.back() = '1';
            EnuerateImpl(result, preCount + 1, n, C);
        }
        result.pop_back();
    }

    counttype CountImpl(int n, int C)
    {
        std::vector<counttype> TN(C + 1, 0); // Use it as circular buffer
        size_t end = TN.size() - 1;
        // End it the last element for the buffer, head is (end + 1) % C

        for (int i = 0; i <= n; ++i)
        {
            counttype tCurrent = 0;
            const auto head = (end + 1) % TN.size();
            if (i < C)
            {
                // 2^i
                tCurrent = 1ull << i;
            }
            else if (i == C)
            {
                // 2^C-1
                tCurrent = (1ull << i) - 1;
            }
            else
            {
                // sum is last element value.
                // T[i] = T[i-1] + ... + T[i-C]
                //      = T[i-1] + T[i-2] + .... + T[i-C] + T[i-C-1] - T[i-C-1]
                //      = T[i-1] + T[i-1] - T[i-C-1]
                //      = 2T[i-1] - T[i-C-1]
                tCurrent = (TN[end % TN.size()] << 1) - TN[head];
            }
            TN[head] = tCurrent;
            end++;
        }

        return TN[end % TN.size()];
    }
};


int main()
{
    Generator gen;
    gen.EnumerateAll(6, 3);
    counttype ret = gen.Count(6, 3);
}